package com.hjx.offer;

import java.util.Optional;

/**
 * 二叉树的下一个节点
 * 题目： 给定一棵二叉树和其中的一个节点， 如何找出中序遍历序列的下一个节点？
 * 树中节点除了有两个分别指向左、右子节点的指针，还有一个指向父节点的指针。
 *
 *                 a
 *              /    \
 *             b      c
 *            / \    / \
 *           d   e  f   g
 *              / \
 *             h   i
 *
 * 题解：
 * 1、树中节点分类
 *    a b   : 有右子树
 *    c e   : 有右子节点 无右子树
 *    d f h : 父节点的左节点 无子节点
 *    i g   : 右节点 无子节点
 * 2、各种类型的节点在中序遍历中的下一节点位置分别是
 *  （1） 有右子树， 右子树的最左节点为下一节点
 *  （2） 有右节点但 无右子树，右子节点为下一节点
 *  （3） 父节点的左节点 无子节点， 父节点为下一节点
 *  （4） 父节点右节点，无子节点， 沿着i的父节点找到某一个父节点 是其父节点的左节点 此时的父节点（a）为下一节点， 若沿着g的父节点找不到则g无下一节点
 *
 */
public class Offer_8 {

    public static void main(String[] args) {
        BinaryTreeNode<String> a = new BinaryTreeNode<String>("a");
        BinaryTreeNode<String> b = new BinaryTreeNode<String>("b");
        BinaryTreeNode<String> c = new BinaryTreeNode<String>("c");
        BinaryTreeNode<String> d = new BinaryTreeNode<String>("d");
        BinaryTreeNode<String> e = new BinaryTreeNode<String>("e");
        BinaryTreeNode<String> f = new BinaryTreeNode<String>("f");
        BinaryTreeNode<String> g = new BinaryTreeNode<String>("g");
        BinaryTreeNode<String> h = new BinaryTreeNode<String>("h");
        BinaryTreeNode<String> i = new BinaryTreeNode<String>("i");

        a.setLeft(b);
        a.setRight(c);
        b.setLeft(d);
        b.setRight(e);
        e.setLeft(h);
        e.setRight(i);
        c.setLeft(f);
        c.setRight(g);

        b.setParent(a);
        c.setParent(a);
        d.setParent(b);
        e.setParent(b);
        h.setParent(e);
        i.setParent(e);
        f.setParent(c);
        g.setParent(c);

        System.out.println("b".equals(getNextInOrder(d).getValue()));
        System.out.println("h".equals(getNextInOrder(b).getValue()));
        System.out.println("e".equals(getNextInOrder(h).getValue()));
        System.out.println("i".equals(getNextInOrder(e).getValue()));
        System.out.println("a".equals(getNextInOrder(i).getValue()));
        System.out.println("f".equals(getNextInOrder(a).getValue()));
        System.out.println("c".equals(getNextInOrder(f).getValue()));
        System.out.println("g".equals(getNextInOrder(c).getValue()));
        System.out.println(null == getNextInOrder(g));

    }

    public static BinaryTreeNode<String> getNextInOrder(BinaryTreeNode<String> node) {
        if (node == null) {
            return null;
        }
        BinaryTreeNode<String> next = null;

        if(node.right != null) {
            /*
             *   （1）（2）两种情况可以合并处理
             * 对于（1） 有右子树则一直遍历找到最左节点 即下一节点
             * 对于（2） 说明没有下级节点 正好符合right.left == null 这一个条件 node.right 即下一节点
             */

            BinaryTreeNode<String> right = node.right;
            while (right.left != null) {
                right = right.left;
            }

            next = right;
        } else if (node.parent != null) {
            // (3)
            if(node.parent.left == node) {
                next = node.parent;
            }
            //(4)
            else if (node.parent.right == node) {
                BinaryTreeNode<String> parent = node.parent;
                while(parent.parent != null && parent.parent.left != parent){
                    parent = parent.parent;
                }
                next = parent.parent;
            }

        }

        return next;
    }
}
